/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/house-robber-ii
   @Language: C++
   @Datetime: 19-04-02 13:52
   */

class Solution {
	int houseRobber(vector<int> &nums, int begin, int end){
		if (nums.size()<begin) return 0;
		int pre=0, ans=nums[begin], temp;
		for(int i=begin+1;i<end;++i){
			temp = max(pre+nums[i],ans);
			pre = ans;
			ans = temp;
		}
		return ans;
	}
public:
	/**
	 * @param nums: An array of non-negative integers.
	 * @return: The maximum amount of money you can rob tonight
	 * Tip:
	 * rob first to last-1;
	 * rob second to last;
	 */
	int houseRobber2(vector<int> &nums) {
		// write your code here
		return max(houseRobber(nums,0,nums.size()-1),houseRobber(nums,1,nums.size()));
	}
};
